#include<vector>
#include<iostream>
using namespace std;
struct Node {
	int val;
	Node* next;
	Node(int val_=-1):val(val_), next(NULL) {

	}
};

class Solution {

	pair<Node*, Node*> split(Node* head) {
		Node tmp1, tmp2;
		Node* first = &tmp1;
		Node* second = &tmp2;
		int count = 0;
		Node* cur = head;
		while (cur != NULL) {
			if (count % 2) {
				second->next = cur;
				second = second->next;
			}
			else {
				first->next = cur;
				first = first->next;
			}
			cur = cur->next;
			++count;
		}
		first->next = NULL;
		second->next = NULL;
		first = tmp1.next;
		second = tmp2.next;
		return pair<Node*, Node*>(first, second);
	}

	Node* reverse(Node* head) {
		if (head == NULL || head->next == NULL) return head;
		Node* rhead = NULL;
		Node* cur = head;
		while (cur != NULL) {
			Node* tmp = cur->next;
			cur->next = rhead;
			rhead = cur;
			cur = tmp;
		}
		return rhead;
	}

	Node* merge(Node* first, Node* second) {
		if (first == NULL) return  second;
		if (second == NULL) return first;
		Node tmp;
		Node* head = &tmp;
		while (first != NULL || second != NULL) {
			if (second == NULL || (first != NULL && first->val > second->val)) {
				head->next = first;
				first = first->next;
				if (second == NULL) break;
			}
			else {
				head->next = second;
				second = second->next;
				if (first == NULL) break;
			}
			head = head->next;
		}
		return tmp.next;
	}


public:
	Node* OddIncreaseEvenDecrease(Node* head) {
		if (head == NULL || head->next == NULL) return head;
		auto tmp = split(head);
		auto first=tmp.first;
		auto second = tmp.second;
		second=reverse(second);
		return merge(first, second);

	}

};

//int main() {
//	vector<int>nums = { 8,1,3,3,2,5,0,7,-1 };
//	Node head;
//	Node* headc = &head;
//	for (auto& num : nums) {
//		Node* node = new Node(num);
//		headc->next = node;
//		headc = headc->next;
//	}
//	Solution sol;
//	Node* node=sol.OddIncreaseEvenDecrease(head.next);
//	while (node != NULL) {
//		std::cout << node->val << " ";
//		node = node->next;
//	}
//
//}


